#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if (n == 0)return NULL;
        ListNode *head,*p;
        int min=0;
        for (int i = 1; i < n; i++)
        {
            if (lists[i] == NULL)
            {
                lists[i--] = lists[--n];
                continue;
            }
            if (lists[i]->val < lists[min]->val)min = i;
        }
        head = p = lists[min];
        if (lists[min] != NULL)lists[min] = lists[min]->next;
        else return NULL;
        if (lists[min] == NULL)
        {
            n--;
            lists[min] = lists[n];
        }
        while (n > 1)
        {
            min = 0;
            for (int i = 1; i < n; i++)
            {
                if (lists[i]->val < lists[min]->val)min = i;
            }
            p->next = lists[min];
            p = p->next;
            if (lists[min] != NULL)lists[min] = lists[min]->next;
            if (lists[min] == NULL)
            {
                n--;
                lists[min] = lists[n];
            }
        }
        if (p != NULL)p->next = lists[0];
        return head;
    }
};
int main()
{
    Solution sol;
}